#define _CRT_SECURE_NO_WARNINGS 1

int PartSort3(int* a, int begin, int end)
{
	int keyi = begin;
	int prev = begin;
	int cur = begin + 1;
	while (cur <= end)
	{
		while (cur <= end && a[cur] >= a[keyi])
		{
			cur++;
		}
		while (prev < cur && a[prev] <= a[keyi])
		{
			prev++;
		}
		Swap(&a[prev], &a[cur]);
	}
	Swap(&a[prev], &a[keyi]);
	keyi = prev;
	return keyi;
}